백준 11444번
오늘 풀어본 문제는 백준의 11444번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
피보나치 수는 $0$과 $1$로 시작한다. $0$번째 피보나치 수는 $0$이고, $1$번째 피보나치 수는 $1$이다. 그 다음 $2$번째 부터는 바로 앞 두 피보나치 수의 합이 된다.
이를 식으로 써보면 $F_n = F_{n-1} + F_{n-2}$ $(n \geq 2)$가 된다.
$n=17$일때 까지 피보나치 수를 써보면 다음과 같다.
$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597$
$n$이 주어졌을 때, $n$번째 피보나치 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 $n$이 주어진다. $n$은 $1,000,000,000,000,000,000$보다 작거나 같은 자연수이다.
출력
첫째 줄에 $n$번째 피보나치 수를 $1,000,000,007$으로 나눈 나머지를 출력한다.
풀이과정
첫 번째 시도
피보나치 수에 대해서 어느정도 알고 있었다. 내가 봐온 예전에 봐왔고 사용했던 풀이들은 주로 Dynamic Programming 을 이용한 풀이가 많았고, bottom-up 방식의 풀이를 시도해보았다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
unsigned long long int n;
cin >> n;
int* fibo = new int[n + 1];
fibo[0] = 0;
fibo[1] = 1;
for (unsigned long long int i = 2; i < n + 1; i++) {
fibo[i] = (fibo[i - 1] + fibo[i - 2]) % 1000000007;
}
cout << fibo[n];
delete[] fibo;
return 0;
}
그러자 런타임 에러 (bad_alloc)이 발생하였다.
두 번째 시도
bad_alloc 이라는 런타임 에러는 처음봤기 때문에 그것이 정확히 무엇을 의미하는지 알기 어려웠다. 그래서 우선은 변수의 타입에 문제가 있나 싶어 int 를 모두 unsigned long long int 로 수정하여 시도해보았다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
unsigned long long int n;
cin >> n;
unsigned long long int* fibo = new unsigned long long int[n + 1];
fibo[0] = 0;
fibo[1] = 1;
for (unsigned long long int i = 2; i < n + 1; i++) {
fibo[i] = (fibo[i - 1] + fibo[i - 2]) % 1000000007;
}
cout << fibo[n];
delete[] fibo;
return 0;
}
그러자 첫 번째 시도 때와 마찬가지로, 런타임 에러 (bad_alloc)이 발생하였다.
세 번째 시도
bad_alloc 에 대해서 좀 더 생각해본 결과, 말 그대로, ‘alloc’에 ‘bad’한 일이 생겼다고 이해했고, 동적할당 과정에서 할당하는 수가 너무 커서 발생하는 문제인가 싶어서 모든 피보나치 수를 기록하는 대신, 가장 최근의 2개의 수만 기록하도록 수정하였다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
unsigned long long int n;
cin >> n;
unsigned long long int fibo0 = 0;
unsigned long long int fibo1 = 1;
unsigned long long int fibo2;
for (unsigned long long int i = 2; i < n + 1; i++) {
fibo2 = (fibo1 + fibo0) % 1000000007;
fibo0 = fibo1;
fibo1 = fibo2;
}
cout << fibo2;
return 0;
}
그러자 이번에는 시간 초과가 발생하였다.
4번째 시도
솔직히 시간 초과를 아예 예상 못한 것은 아니었다. 예전에 듣기로, 이런 피보나치 수 문제를 해결하는 방법으로 DP를 이용한 방법보다 빠른 방법이 있다고 언핏 들은 것 같기는 했었다.
우리가 지금까지 봐온 코드의 방식은, 생긴 건 조금씩 달라도 결국 앞의 두 수를 계속해서 더해 나아가는 방식으로 이루어지기 때문에, 시간 복잡도가 $O(n)$이 나오게 된다. 그런데 $n$이 너무 컸던 나머지, 시간 초과가 발생한 것이다.
이를 해결하기 위한 방법으로 들었던 내용은, 행렬을 이용하는 것이다. 구하고자 하는 $n$ 번째 피보나치 수를 알아내기 위한 방법으로, 이런 식을 사용할 수가 있다.
\[\begin{pmatrix} a_n \\ a_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} a_{n-1} \\ a_{n-2} \end{pmatrix}\]이 점화식을 이리저리 잘 굴리게 되면, 이런 결과를 얻을 수 있게 된다.
\[\begin{pmatrix} a_n \\ a_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n-1} \begin{pmatrix} a_{1} \\ a_{0} \end{pmatrix}\]여기서 $a_0$ 과 $a_1$ 은 문제에서 나온 것 처럼 $0$과 $1$ 이다.
식을 보면 행렬에 $n-1$ 제곱이 되어있는데, 이것을 그냥 곱하지 않고 효율적으로 곱하는 방법이 있다. 행렬을 곱하는 과정에서 두 개의 큰 덩이로 나누고, 그 덩이를 두 번 곱하는 것이다.
이런 방식으로 구하게 되면, 시간 복잡도는 $O(\log n)$이 된다. 자세한 원리 설명 등은 생략하도록 하겠다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
struct Matrix {
unsigned long long int leftUp, rightUp, leftDown, rightDown;
Matrix(unsigned long long int leftUp, unsigned long long int rightUp, unsigned long long int leftDown, unsigned long long int rightDown) : leftUp(leftUp), rightUp(rightUp), leftDown(leftDown), rightDown(rightDown) {}
Matrix operator*(const Matrix& other) {
unsigned long long int a, b, c, d, e, f, g, h;
a = this->leftUp;
b = this->rightUp;
c = this->leftDown;
d = this->rightDown;
e = other.leftUp;
f = other.rightUp;
g = other.leftDown;
h = other.rightDown;
Matrix result((a * e + b * g) % 1000000007, (a * f + b * h) % 1000000007, (c * e + d * g) % 1000000007, (c * f + d * h) % 1000000007);
return result;
}
pair<unsigned long long int, unsigned long long int> operator*(const pair<unsigned long long int, unsigned long long int>& other) {
unsigned long long int a, b, c, d, e, f;
a = this->leftUp;
b = this->rightUp;
c = this->leftDown;
d = this->rightDown;
e = other.first;
f = other.second;
pair<unsigned long long int, unsigned long long int> result = { (a * e + b * f) % 1000000007, (c * e + d * f) % 1000000007 };
return result;
}
};
Matrix matPow(Matrix A, unsigned long long int n);
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
unsigned long long int n;
cin >> n;
pair<unsigned long long int, unsigned long long int> fibo = { 1, 0 };
fibo = matPow({ 1, 1, 1, 0 }, n - 1) * fibo;
cout << fibo.first;
return 0;
}
Matrix matPow(Matrix A, unsigned long long int n) {
if (n == 0) {
return { 1, 0, 0, 1 };
}
if (n == 1) {
return A;
}
else {
if (n % 2 == 0) {
return matPow(A, n / 2) * matPow(A, n / 2);
}
else {
return matPow(A, n / 2) * matPow(A, n / 2) * A;
}
}
}
실행 결과는 여전히 시간 초과였다.
5번째 시도
이론상 맞게 적용한 것 같고, 제공된 테스트 케이스도 맞게 돌아가기 때문에 구현에 틀린게 없다고 생각했었다. 그러나 코드를 다시 확인한 결과, ‘두 덩이’로 나눈 것은 좋은데, ‘두 덩이’를 ‘한 번 구해서 두 번’ 사용하는 것이 아닌, ‘각각 구해서 곱하는’ 이상한 방식을 사용하고 있었다. 그래서 임시로 한 덩이를 저장해줄 변수를 만들고 그 변수를 두 번 곱하도록 수정하였다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
struct Matrix {
unsigned long long int leftUp, rightUp, leftDown, rightDown;
Matrix(unsigned long long int leftUp, unsigned long long int rightUp, unsigned long long int leftDown, unsigned long long int rightDown) : leftUp(leftUp), rightUp(rightUp), leftDown(leftDown), rightDown(rightDown) {}
Matrix operator*(const Matrix& other) {
unsigned long long int a, b, c, d, e, f, g, h;
a = this->leftUp;
b = this->rightUp;
c = this->leftDown;
d = this->rightDown;
e = other.leftUp;
f = other.rightUp;
g = other.leftDown;
h = other.rightDown;
Matrix result((a * e + b * g) % 1000000007, (a * f + b * h) % 1000000007, (c * e + d * g) % 1000000007, (c * f + d * h) % 1000000007);
return result;
}
pair<unsigned long long int, unsigned long long int> operator*(const pair<unsigned long long int, unsigned long long int>& other) {
unsigned long long int a, b, c, d, e, f;
a = this->leftUp;
b = this->rightUp;
c = this->leftDown;
d = this->rightDown;
e = other.first;
f = other.second;
pair<unsigned long long int, unsigned long long int> result = { (a * e + b * f) % 1000000007, (c * e + d * f) % 1000000007 };
return result;
}
};
Matrix matPow(Matrix A, unsigned long long int n);
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
unsigned long long int n;
cin >> n;
pair<unsigned long long int, unsigned long long int> fibo = { 1, 0 };
fibo = matPow({ 1, 1, 1, 0 }, n - 1) * fibo;
cout << fibo.first;
return 0;
}
Matrix matPow(Matrix A, unsigned long long int n) {
if (n == 0) {
return { 1, 0, 0, 1 };
}
if (n == 1) {
return A;
}
else {
Matrix half = matPow(A, n / 2);
if (n % 2 == 0) {
return half * half;
}
else {
return half * half * A;
}
}
}
그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.
마무리
이 문제는 피보나치 수 6인데, 앞의 1, 2, 3, 4, 5는 어디갔는지 모르겠다.
이미 눈치챈 사람도 있겠지만, 이 문제는 solved.ac 기준으로 CLASS 4에 해당하는 문제이다. 이제까지는 CLASS 3에 해당하는 문제들만 풀어왔었는데, CLASS 2의 모든 문제를 해결하고 나서는 이제 CLASS 4 문제들도 열심히 풀어보려고 한다.
이제까지는 매일 CLASS 3 한 문제, CLASS 2 한 문제 이상 풀어왔다. CLASS 2의 내용들은 비교적 단순한 것들이기도 해서 일일히 글로 남기지는 않았다. 물론, CLASS 2의 문제들을 밀면서 배운 내용들도 나름 있었지만, 모든 문제를 글로 남겨야 했다면 내 손가락이 남아나지 않았을 것이다. 그래서 가장 어려운 문제인 편인 CLASS 3의 문제들만 글로 남겨왔던 것이다.
이제는 CLASS 4 한 문제, CLASS 3 한 문제 이상을 목표로 잡고 풀어보려고 한다. 만약 상황이 어렵다면, CLASS 3 한 문제만 풀고 글을 쓰게 될 수도 있겠지만, 최대한 CLASS 4 위주로 글을 올려보도록 하겠다.
오늘 문제에서 배웠던 것, 정확히 말하자면, 기억해 냈던 것은 분할정복법이다. 분할정복법은 말 그대로 분할에서 정복한다는 의미로, 분할이 ‘덩이’를 나누는 과정이고, 그 둘을 다시 ‘곱하여’ 정복한 것이다. 앞으로 자주 보게될 유형일 것 같으니 제대로 기억해 두어야겠다.
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/11444